home *** CD-ROM | disk | FTP | other *** search
/ Gekkan Dennou Club 140 / Gekkan Dennou Club - 2000.1 Vol. 140 (Japan) (Track 1).bin / docs / perl / eight.pl < prev    next >
Encoding:
Text File  |  1999-10-29  |  2.0 KB  |  93 lines
  1. #
  2. # eight.pl : ８パズル
  3. #
  4. # 座標
  5. # 0 1 2
  6. # 3 4 5
  7. # 6 7 8
  8. #
  9. #
  10.  
  11.  
  12. # 外部変数定義
  13. $end_state = "123456780";  # 終了状態
  14. @state = ();               # 盤面を格納（文字列で表現)
  15. @move_start = ();          # i 手目のスタート位置
  16. @prev_state = ();          # 一つ手前の状態
  17. %check_state = ();         # 同一局面チェック用ハッシュ
  18. @adjacent = (
  19.   [1, 3],       # 0
  20.   [0, 4, 2],    # 1
  21.   [1, 5],       # 2
  22.   [0, 4, 6],    # 3
  23.   [1, 3, 5, 7], # 4
  24.   [2, 4, 8],    # 5
  25.   [3, 7],       # 6
  26.   [4, 6, 8],    # 7
  27.   [5, 7]        # 8
  28. );
  29.  
  30. # 盤面を表示
  31. sub print_state {
  32.   my $s = shift;
  33.   my $i;
  34.   for( $i = 0; $i < 9; $i += 3 ){
  35.     print substr( $s, $i, 3 ), "\n";
  36.   }
  37.   print "\n";
  38. }
  39.  
  40. # 正解を逆順で表示
  41. sub print_history {
  42.   my $n = shift;
  43.   print_state( $end_state );
  44.   while( $n != -1 ){
  45.     my $s = $state[$n];
  46.     &print_state( $state[$n] );
  47.     $n = $prev_state[$n];
  48.   }
  49. }
  50.  
  51. # 探索
  52. sub search {
  53.   my $move = 1;
  54.   my $count = 1;
  55.   $state[0] = shift;
  56.   $move_start[0] = 0;
  57.   $prev_state[0] = -1;
  58.   $check_state{$state[0]} = 1;
  59.   while( $count > $move_start[$move - 1] ){
  60.     my $i = $move_start[$move - 1];
  61.     print STDERR "$move 手の検索・・・\n\n";
  62.     $move_start[$move] = $count;
  63.     for( ; $i < $move_start[$move]; $i++ ){
  64.       my $zp = index( $state[$i], '0' );          # 0 の位置を求める
  65.  
  66.       foreach $np ( @{ $adjacent[$zp] } ){
  67.         my $c  = substr( $state[$i], $np, 1 );    # 移動する文字を取り出す
  68.         my $ns = $state[$i];                      # 状態をコピーする
  69.         $ns =~ s/([0$c])(.*)([0$c])/$3$2$1/;      # 0 と交換する
  70.  
  71.         if( $end_state eq $ns ){
  72.           # 解けた
  73.           &print_history( $i );
  74.           return;                                 # 終了
  75.         } elsif( !$check_state{$ns} ){
  76.           # 同じ状態はない
  77.           $state[$count] = $ns;                   # 状態セット
  78.       $check_state{$ns} = 1;
  79.           $prev_state[$count++] = $i;             # 履歴セット
  80.         }
  81.       }
  82.     }
  83.     # 次の移動
  84.     $move++;
  85.   }
  86. }
  87.  
  88.  
  89. &search( "647850321" );
  90.  
  91. # end of file
  92.  
  93.